Understanding Leakage in Searchable Encryption: a Quantitative Approach
Authors: Alexandra Boldyreva (Georgia Institute of Technology), Zichen Gui (ETH Zurich), Bogdan Warinschi (Dfinity & University of Bristol)
Volume: 2024
Issue: 4
Pages: 503–524
DOI: https://doi.org/10.56553/popets-2024-0127
Abstract: Searchable encryption, or more generally, structured encryption, permits search over encrypted data. It is an important cryptographic tool for securing cloud storage. The standard security notion for structured encryption mandates that a protocol leaks nothing about the data or queries, except for some allowed leakage, defined by the leakage function. This is due to the fact that some leakage is unavoidable for efficient schemes.\\ Unfortunately, it was shown by numerous works that even innocuous-looking leakage can often be exploited by attackers to undermine users' privacy and recover their queries and/or data, despite the structured encryption schemes being provably secure. Nevertheless, the standard security remains the go-to notion used to show the 'security' of structured encryption schemes. While it is not likely that researchers will design practical structured encryption schemes with no leakage, it is not satisfactory that very few works study ways to assess leakage.This work proposes a novel framework to quantify leakage. Our methodology is inspired by the quantitative information flow, and we call our method q-leakage analysis. We show how $q$-leakage analysis is related to the standard security. We also demonstrate the usefulness of q-leakage analysis by analyzing the security of two existing schemes with complex leakage functions.
Keywords: searchable encryption, structured encryption, data privacy, leakage, cloud storage security, provable security
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
